#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INFINITY 100

class Graph{
    int VertexNum;//节点
    vector<char> Vertex;//节点
    vector<vector<int>> Edge;//邻接矩阵
    vector<vector<char>> Path;//路径
    vector<int> Dest;//目标
public:
    Graph(int vertexnum, const vector<char>& vertex, const vector<vector<int>>& edge);//构造函数
    ~Graph() = default;//删除函数
    void ShowGraph(void);
    void ShortestPath(char startVexChar);
    void ShowPath(void);
};

Graph::Graph(int vertexnum, const vector<char>& vertex, const vector<vector<int>>& edge)
    : VertexNum(vertexnum), Vertex(vertex), Edge(edge), 
    Path(vertexnum, vector<char>(vertexnum)), Dest(vertexnum, INFINITY) 
{
    for(int i=0; i<VertexNum; i++)
    {
        for(int j=0; j<VertexNum; j++)
        {
            if(Edge[i][j] == -1)
            {
                Edge[i][j] = INFINITY;
            }
        }
    }
}

void Graph::ShowGraph(void)
{
    for(int i=0; i<VertexNum; i++)
    {
        cout<<Vertex[i]<<" ";
    }
    cout<<endl;
    for(int i=0; i<VertexNum; i++)
    {
        for(int j=0; j<VertexNum; j++)
        {
            cout<<Edge[i][j]<<" ";
        }
        cout<<endl;
    }
}

void Graph::ShortestPath(char startVexChar)
{
    auto it = find(Vertex.begin(), Vertex.end(), startVexChar);
    if(it == Vertex.end())
    {
        cout << "Start vertex not found" << endl;
        return;
    }
    int startVexIndex = distance(Vertex.begin(), it);
    vector<bool> visited(VertexNum, false);//被访问标志位数组初始化
    visited[startVexIndex] = true;
    Dest[startVexIndex] = 0;

    for(int i=0; i<VertexNum; i++)
    {
        Dest[i] = Edge[startVexIndex][i];
        if(Dest[i] != INFINITY && i != startVexIndex)
        {
            Path[i].push_back(startVexChar);
            Path[i].push_back(Vertex[i]);
        }
    }
    Dest[startVexIndex] = 0;
    for(int i=1; i<VertexNum; i++)
    {
        int min = INFINITY;
        int u = 0;
        for(int j=0; j<VertexNum; j++)
        {
            if(!visited[j] && Dest[j]<min)
            {
                min = Dest[j];
                u = j;
            }
        }
        visited[u] = true;

        for(int k=0; k<VertexNum; k++)
        {
            if(!visited[k] && Edge[u][k]<INFINITY)
            {
                if(Dest[u] + Edge[u][k] < Dest[k])
                {
                    Dest[k] = Dest[u] + Edge[u][k];
                    Path[k].clear();
                    Path[k].insert(Path[k].end(), Path[u].begin(), Path[u].end());
                    Path[k].push_back(Vertex[k]);
                }
            }
        }
    }
}

void Graph::ShowPath(void)
{
    for(int i=0; i<VertexNum; i++)
    {
        cout <<Vertex[i] << ": ";
        for(auto j : Path[i])
        {
            if(j != '\0')  // Add this line
            {
                cout << j;
                if(j != Path[i].back())
                    cout << " -> ";
            }
        }
        cout << " | Distance: " << Dest[i] << endl;
    }
}

int main(int argc, char *argv[])
{
    vector<vector<int>> edge = {
        {-1,5,-1,7,15},
        {-1,-1,5,-1,-1},
        {-1,-1,-1,-1,1},
        {-1,-1,2,-1,-1},
        {-1,-1,-1,-1,-1}
    };
    vector<char> vertex = {'a', 'b', 'c', 'd', 'e'};
    Graph a(5, vertex, edge);
    //a.ShowGraph();
    a.ShortestPath('a');
    a.ShowPath();
}